Binary tree

Not to be confused with B-tree.
A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is neither a sorted nor a balanced binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child.

Binary trees are commonly used to implement binary search trees and binary heaps.

Contents

Definitions for rooted trees

Types of binary trees

Note that this terminology often varies in the literature, especially with respect to the meaning "complete" and "full".

Properties of binary trees

Proof

proof: n0=n2+1

   Let n = the total number of nodes
       B = the branches in T
       n0, n1, n2 represent the nodes with no children, single child, and two children respectively.

   B = n - 1
   B = n1 + 2*n2 
   n = n1+ 2*n2 + 1
   n = n0 + n1 + n2
   n1+ 2*n2 + 1 = n0 + n1 + n2 ==> n0 = n2 + 1

Type theory

In type theory, a binary tree with nodes of type A is defined inductively as TA = μα. 1 + A × α × α.

Definition in graph theory

For each binary tree data structure, there is equivalent rooted binary tree in graph theory.

Graph theorists use the following definition: A binary tree is a connected acyclic graph such that the degree of each vertex is no more than three. It can be shown that in any binary tree of two or more nodes, there are exactly two more nodes of degree one than there are of degree three, but there can be any number of nodes of degree two. A rooted binary tree is such a graph that has one of its vertices of degree no more than two singled out as the root.

With the root thus chosen, each vertex will have a uniquely defined parent, and up to two children; however, so far there is insufficient information to distinguish a left or right child. If we drop the connectedness requirement, allowing multiple connected components in the graph, we call such a structure a forest.

Another way of defining binary trees is a recursive definition on directed graphs. A binary tree is either:

This also does not establish the order of children, but does fix a specific root node.

Combinatorics

The groupings of pairs of nodes in a tree can be represented as pairs of letters, surrounded by parenthesis. Thus, (a b) denotes the binary tree whose left subtree is a and whose right subtree is b. Strings of balanced pairs of parenthesis may therefore be used to denote binary trees in general. The set of all possible strings consisting entirely of balanced parentheses is known as the Dyck language.

Given n nodes, the total number of ways in which these nodes can be arranged into a binary tree is given by the Catalan number C_n. For example, C_2=2 declares that (a 0) and (0 a) are the only binary trees possible that have two nodes, and C_3=5 declares that ((a 0) 0), ((0 a) 0), (0 (a 0)), (0 (0 a)), and (a b) are the only five binary trees possible that have 3 nodes. Here 0 represents a subtree that is not present.

The ability to represent binary trees as strings of symbols and parentheses implies that binary trees can represent the elements of a magma. Conversely, the set of all possible binary trees, together with the natural operation of attaching trees to one-another, forms a magma, the free magma.

Given a string representing a binary tree, the operators to obtain the left and right subtrees are sometimes referred to as car and cdr.

Methods for storing binary trees

Binary trees can be constructed from programming language primitives in several ways.

Nodes and references

In a language with records and references, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child. Sometimes it also contains a reference to its unique parent. If a node has fewer than two children, some of the child pointers may be set to a special null value, or to a special sentinel node.

In languages with tagged unions such as ML, a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple of data, left child, and right child, and the other of which is a "leaf" node, which contains no data and functions much like the null value in a language with pointers.

Ahnentafel list

Binary trees can also be stored as an implicit data structure in arrays, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its children are found at indices 2i + 1(for the left child) and 2i +2(for the right), while its parent (if any) is found at index \left \lfloor \frac{i-1}{2} \right \rfloor (assuming the root has index zero). This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal. However, it is expensive to grow and wastes space proportional to 2h - n for a tree of height h with n nodes.

A small complete binary tree stored in an array

A binary tree can also be represented in the form of array as well as adjacency linked list. In the case of array, each node(root,left,right) is simply placed in the index and there is no connection mentioned about the relationship between parents and children. But In linked list representation we can find the relationship between parent and children. In array representation the nodes are accessed by calculating the index. This method is used in languages like FORTRAN which doesn't have dynamic memory allocation. We can't insert a new node into array implemented binary tree with ease, but this is easily done when using a binary tree implemented as linked list.

Methods of iterating over binary trees

Often, one wishes to visit each of the nodes in a tree and examine the value there. There are several common orders in which the nodes can be visited, and each has useful properties that are exploited in algorithms based on binary trees:

Pre-order, in-order, and post-order traversal

Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root. If the root node is visited before its subtrees, this is pre-order; if after, post-order; if between, in-order. In-order traversal is useful in binary search trees, where this traversal visits the nodes in increasing order.

Depth-first order

In depth-first order, we always attempt to visit the node farthest from the root that we can, but with the caveat that it must be a child of a node we have already visited. Unlike a depth-first search on graphs, there is no need to remember all the nodes we have visited, because a tree cannot contain cycles. Pre-order is a special case of this. See depth-first search for more information.

Breadth-first order

Contrasting with depth-first order is breadth-first order, which always attempts to visit the node closest to the root that it has not already visited. See Breadth-first search for more information. Also called a level-order traversal.

Encodings

Succinct encodings

A succinct data structure is one which takes the absolute minimum possible space, as established by information theoretical lower bounds. The number of different binary trees on n nodes is \mathrm{C}_{n}, the nth Catalan number (assuming we view trees with identical structure as identical). For large n, this is about 4^{n}; thus we need at least about \log_{2}4^{n} = 2n bits to encode it. A succinct binary tree therefore would occupy only 2 bits per node.

One simple representation which meets this bound is to visit the nodes of the tree in preorder, outputting "1" for an internal node and "0" for a leaf. [1] If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder. This function accomplishes this:

function EncodeSuccinct(node n, bitstring structure, array data) {
    if n = nil then
        append 0 to structure;
    else
        append 1 to structure;
        append n.data to data;
        EncodeSuccinct(n.left, structure, data);
        EncodeSuccinct(n.right, structure, data);
}

The string structure has only 2n + 1 bits in the end, where n is the number of (internal) nodes; we don't even have to store its length. To show that no information is lost, we can convert the output back to the original tree like this:

function DecodeSuccinct(bitstring structure, array data) {
    remove first bit of structure and put it in b
    if b = 1 then
        create a new node n
        remove first element of data and put it in n.data
        n.left = DecodeSuccinct(structure, data)
        n.right = DecodeSuccinct(structure, data)
        return n
    else
        return nil
}

More sophisticated succinct representations allow not only compact storage of trees but even useful operations on those trees directly while they're still in their succinct form.

Encoding general trees as binary trees

There is a one-to-one mapping between general ordered trees and binary trees, which in particular is used by Lisp to represent general ordered trees as binary trees. To convert a general ordered tree to binary tree, we only need to represent the general tree in left child-sibling way. The result of this representation will be automatically binary tree, if viewed from a different perspective. Each node N in the ordered tree corresponds to a node N' in the binary tree; the left child of N' is the node corresponding to the first child of N, and the right child of N' is the node corresponding to N 's next sibling --- that is, the next node in order among the children of the parent of N. This binary tree representation of a general order tree is sometimes also referred to as a Left child-right sibling binary tree (LCRS tree), or a Doubly-chained tree, or a Filial-Heir chain.

One way of thinking about this is that each node's children are in a linked list, chained together with their right fields, and the node only has a pointer to the beginning or head of this list, through its left field.

For example, in the tree on the left, A has the 6 children {B,C,D,E,F,G}. It can be converted into the binary tree on the right.

An example of converting an n-ary tree to a binary tree

The binary tree can be thought of as the original tree tilted sideways, with the black left edges representing first child and the blue right edges representing next sibling. The leaves of the tree on the left would be written in Lisp as:

(((N O) I J) C D ((P) (Q)) F (M))

which would be implemented in memory as the binary tree on the right, without any letters on those nodes that have a left child.

See also

Notes

  1. ↑ http://www.laynetworks.com/cs04.htm
  2. ↑ http://www.laynetworks.com/cs04.htm
  3. ↑ "perfect binary tree". NIST. http://www.nist.gov/dads/HTML/perfectBinaryTree.html. 
  4. ↑ "complete binary tree". NIST. http://www.nist.gov/dads/HTML/completeBinaryTree.html. 
  5. ↑ Mehta, Dinesh; Sartaj Sahni (2004). Handbook of Data Structures and Applications. Chapman and Hall. ISBN 1584884355. 

References

External links

Trees in computer science
Binary trees
Binary search tree (BST) · Van Emde Boas tree · Cartesian tree · Top Tree · T-tree
Self-balancing binary search trees
Red-black tree · AVL tree · AA tree · Splay tree · Scapegoat tree · Treap
B-trees
B+ tree · B*-tree · UB-tree · 2-3 tree · 2-3-4 tree · (a,b)-tree · Dancing tree · Htree · Bx-tree
Tries
Suffix tree · Radix tree · Ternary search tree
Binary space partitioning (BSP) trees
Quadtree · Octree · kd-tree (implicit) · VP-tree
Non-binary trees
Exponential tree · Fusion tree · Interval tree · PQ tree · Range tree · SPQR tree
Spatial data partitioning trees
R-tree · R+ tree · R* tree · X-tree · M-tree · Segment tree · Fenwick tree · Hilbert R-tree
Other trees
Heap · Hash tree · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance